package Solutions

import "sort"

func searchMatrix_(matrix [][]int, target int) bool {
	if len(matrix) == 0 {
		return false
	}
	r := sort.SearchInts(matrix[0], target)
	if r < len(matrix[0]) && matrix[0][r] == target {
		return true
	}
	j := sort.Search(len(matrix), func(i int) bool {
		if len(matrix[i]) == 0 {
			return false
		}
		return matrix[i][0] > target
	})
	for i := 0; i < j; i++ {
		k := sort.SearchInts(matrix[i][0:r], target)
		if k < r && matrix[i][k] == target {
			return true
		}
	}
	return false

}
